import java.util.StringTokenizer;
import java.util.Stack;

public class MyDC {
    private final char ADD = '+';
    private final char SUBTRACT = '-';
    private final char MULTIPLY = '*';
    private final char DIVIDE = '/';
    private final char LPARE = '(';
    private final char RPARE = ')';
    private Stack<Rational> stack;
    private Stack<Character> stacktwo;

    public MyDC() {
        stack = new Stack<Rational>();
        stacktwo = new Stack<Character>();
    }

    public Rational evaluate(String expr) {
        int i;
        Rational op1 = new Rational();
        Rational op2 = new Rational();
        Rational result = new Rational();
        result.setNumerator(0);
        char token[] = expr.toCharArray();
        for (i = 0; i < token.length; i++) {
            if (isOperator(token[i])) {
                op2 = (Rational) stack.pop();
                op1 = (Rational) stack.pop();
                result = evalSingleOp(token[i], op1, op2);
                stack.push(result);//将结果压栈
            } else {
                Rational num = new Rational();
                num.setNumerator(token[i] - '0');
                stack.push(num);
            }
        }

        return result;
    }

    private boolean isOperator(char token) {
        return (token == '+' || token == '-' ||
                token == '*' || token == '/');
    }

    private Rational evalSingleOp(char operation, Rational op1, Rational op2) {
        Rational result = new Rational();
        result.setNumerator(0);
        switch (operation) {
            case ADD:
                result = op1.add(op2);
                break;
            case SUBTRACT:
                result = op1.sub(op2);
                break;
            case MULTIPLY:
                result = op1.muti(op2);
                break;
            case DIVIDE:
                result = op1.div(op2);
        }

        return result;
    }

    public String trans(String before) {
        int i, j = 0;
        char step[] = before.toCharArray();
        char after[] = new char[step.length];
        for (i = 0; i < step.length; i++) {
            if (step[i] >= '0' && step[i] <= '9') {
                after[j] = step[i];
                j++;
                if (i == (step.length) - 1) {
                    while (stacktwo.empty() == false) {
                        after[j] = stacktwo.pop();
                        j++;
                    }
                }
            } else if (stacktwo.empty() || step[i] == '(' || stacktwo.peek() == '(' || stacktwo.peek() == ')') {
                stacktwo.push(new Character(step[i]));
                if (i == (step.length) - 1) {
                    while (stacktwo.empty() == false) {
                        after[j] = stacktwo.pop();
                        j++;
                    }
                }
            } else if (step[i] == ')') {
                while (stacktwo.peek() != '(') {
                    after[j] = stacktwo.pop();
                    j++;
                }
                stacktwo.pop();
                if (i == (step.length) - 1) {
                    while (stacktwo.empty() == false) {
                        after[j] = stacktwo.pop();
                        j++;
                    }
                }
            } else {
                switch (step[i]) {
                    case ADD:
                    case SUBTRACT: {
                        while (stacktwo.peek() == '*' || stacktwo.peek() == '/' || stacktwo.peek() == '+' || stacktwo.peek() == '-') {
                            after[j] = stacktwo.pop();
                            j++;
                            if (stacktwo.empty()) {
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                    case MULTIPLY:
                    case DIVIDE: {
                        while (stacktwo.peek() == '*' || stacktwo.peek() == '/') {
                            after[j] = stacktwo.pop();
                            j++;
                            if (stacktwo.empty()) {
                                break;
                            }
                        }
                        stacktwo.push(new Character(step[i]));
                        break;
                    }
                }
                if (i == (step.length) - 1) {
                    while (stacktwo.empty() != false) {
                        after[j] = stacktwo.pop();
                        j++;
                    }
                }
            }
        }
        String str = new String(after);
        return str;
    }

}

